#ifndef LEETCODE_CN_CPP_PROBLEMS_820_H
#define LEETCODE_CN_CPP_PROBLEMS_820_H

#include <algorithm>
#include <string>
#include <string_view>
#include <vector>

using namespace std;

namespace problem_820
{

class Solution
{
private:
    const bool isSuffix(const string_view &str, const string_view &suf) const
    {
        return search(str.rbegin(), str.rend(), suf.rbegin(), suf.rend()) == str.rbegin();
    }

public:
    int minimumLengthEncoding(vector<string> &words)
    {
        if (words.empty())
            return 0;
        vector<string_view> _words;
        for (auto &word : words)
            _words.emplace_back(word);
        sort(_words.begin(), _words.end(),
             [](const string_view &a, const string_view &b) -> bool {
                 return lexicographical_compare(a.rbegin(), a.rend(), b.rbegin(), b.rend());
             });
        int result = 0, pre = _words.front().size();
        for (int i = 1; i < _words.size(); ++i)
        {
            if (!isSuffix(_words[i], _words[i - 1]))
                result += pre + 1;
            pre = _words[i].size();
        }
        return result + pre + 1;
    }
};

} // namespace problem_820

#endif //LEETCODE_CN_CPP_PROBLEMS_820_H
